import collections


# O(n)空间复杂度
# class Solution(object):
#     def findDuplicates(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[int]
#         """
#         out = []
#         c = collections.defaultdict(int)
#         for item in nums:
#             c[item] += 1
#             if c[item] == 2:
#                 out.append(item)
#         return out


# O(1)空间复杂度
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        out = []
        for i in range(n):
            if nums[abs(nums[i]) - 1] < 0:
                out.append(abs(nums[i]))
            else:
                nums[abs(nums[i]) - 1] = - nums[abs(nums[i]) - 1]
        return out


# O(1)空间复杂度
# class Solution(object):
#     def findDuplicates(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[int]
#         """
#         n = len(nums)
#         out = []
#
#         for i in range(n):
#             while nums[i] != nums[nums[i] - 1]:
#                 temp = nums[i] - 1
#                 nums[i] = nums[temp]
#                 nums[temp] = temp + 1
#         for i in range(n):
#             if nums[i] != i + 1:
#                 out.append(nums[i])
#         return out

# O(1)空间复杂度
# class Solution(object):
#     def findDuplicates(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[int]
#         """
#         n = len(nums)
#         out = []
#
#         for i in range(n):
#             while nums[i] != nums[nums[i] - 1]:
#                 temp = nums[i] - 1
#                 nums[i] = nums[temp]
#                 nums[temp] = temp + 1
#         for i in range(n):
#             if nums[i] != i + 1:
#                 out.append(nums[i])
#         return out


data = Solution()
nums = [10, 2, 5, 10, 9, 1, 1, 4, 3, 7]
print(data.findDuplicates(nums))
